package com.algorithm.learning.sort;

import java.util.Arrays;

/**
 * @program: algorithm-learning
 * @description: 选择排序
 * @author: YuKai Fan
 * @create: 2024/8/17 22:30
 **/
public class SelectionSort {


    public static void main(String[] args) {
        SelectionSort selectionSort = new SelectionSort();
        int[] nums = {5,1,1,2,0,0};
        System.out.println(Arrays.toString(selectionSort.sortArray(nums)));
    }

    /**
     * 选择排序
     *
     * 从第一个元素一个一个比较，遇到小于的就进行交换，这样效果如下:
     * 第一次遍历，最小值就是放到第一位
     * 第二次遍历，会从剩下的元素开始，即第二小的元素放在第二位
     *
     * 以此类推
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        // 最后一轮只有一个元素，一定是最大的元素，因此写 i < len - 1
        for (int i = 0; i < nums.length - 1; i++) {
            int minIndex = i;
            // 在 [i + 1, len - 1] 区间里选择最小的元素的下标
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
                int tmp = nums[i];
                nums[i] = nums[minIndex];
                nums[minIndex] = tmp;
            }
        }
        return nums;
    }
}
